package pro.softzhang.algo.lc700;


import pro.softzhang.algo.flag.knowledge.KSlidingWindow;

/**
 * 713. 乘积小于 K 的子数组
 * https://leetcode.cn/problems/subarray-product-less-than-k
 */
@KSlidingWindow
public class LC713_SubarrayProductLessThanK {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        int k = 3;
        int min = new Solution().numSubarrayProductLessThanK(nums, k);
        System.out.println(min);
    }

    /**
     *
     */
    static
    class Solution {
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            int count = 0, product = 1, left = 0;
            for (int right = 0; right < nums.length; right++) {
                product *= nums[right];
                while (product >= k) {
                    product /= nums[left];
                    left++;
                }
                count += right >= left ? right - left + 1 : 0;
            }
            return count;
        }
    }

    static
    class Solution1 {
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            if (k <= 1) return 0;

            int res = 0, product = 1, left = 0;
            for (int right = 0; right < nums.length; right++) {
                product *= nums[right];
                while (product >= k) {
                    product /= nums[left];
                    left++;
                }
                res += right - left + 1;
            }
            return res;
        }
    }
}
